'''
三堆石头
只能拿斐波那契数列中的石头
'''
import random
from functools import cache


def g(a, b, c):
    fab = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]
    @cache
    def f(a, b, c):
        if a + b + c == 0:
            return False
        res = False
        for pick in fab:
            if pick <= a:
                res = res or not f(a - pick, b, c)
            if pick <= b:
                res = res or not f(a, b - pick, c)
            if pick <= c:
                res = res or not f(a, b, c - pick)
            if res: return True
        return False
    return f(a, b, c)


def f(a, b, c):
    maxi = max(a, b, c)
    # sg 0: 0
    # sg 1: 1   0:0
    # sg 2: 2   0:0,1:1
    # sg 3: 3   0:0,1:1,2:2
    # sg 4: 0   1:1,2:2,3:3
    # sg 5: 1   0:0,2:2,3:3,4:0
    # sg 6: 2   1:1,3:3,4:0,5:1
    fab = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]
    sg = [0] * (maxi + 1)
    for i in range(1, maxi + 1):
        appeared = [False] * (i + 1)
        for j in fab:
            if i - j < 0: break
            appeared[sg[i - j]] = True
            # appeared[i - j] = True
        for s in range(i + 1):
            if not appeared[s]:
                sg[i] = s
                break
    # print(a, b, c)
    # print(*[(f'sg({i})', s) for i, s in enumerate(sg)])
    return (sg[a] ^ sg[b] ^ sg[c]) != 0


def h(a, b, c):
    # return ((a % (limit + 1)) ^ (b % (limit + 1))) != 0
    return False


a, b, c = 2, 300, 7
print(f(a, b, c))
print(g(a, b, c))
for _ in range(100):
    maxi = 100
    a = random.randint(1, maxi)
    b = random.randint(1, maxi)
    c = random.randint(1, maxi)
    r1 = f(a, b, c)
    r2 = g(a, b, c)
    if not r1 == r2:
        print(a, b, c, sep=', ')
        print(r1, r2)
        break
print('done')
